
#include<iostream>
#include<vector>



using namespace std;

class Solution{

    public:
    int uniquePathWithObstacles(vector<vector<int>> & obstacleGrid){

        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        if (obstacleGrid[0][0]){
            return 0;
        }
        
        vector<vector<int>> dp(m, vector<int>(n, 0));
        dp[0][0] = 1;
        // for(int i = 1; i < )
        for(int i = 0; i < m; i++){
            if (obstacleGrid[i][0] != 1)
            {
                dp[i][0] = 1;
            }else{
                break;
            }
            
        }
        for(int j = 0; j < n; j++){
            if(obstacleGrid[0][j] != 1){

                dp[0][j] = 1;
            }else{
                break;
            }
        }

        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                if(!obstacleGrid[i][j]){
                    dp[i][j] = dp[i-1][j] + dp[i][j - 1];
                }

            }
        }

        return dp[m - 1][n - 1];

    }

};

